Information-theoretic cryptography is chock-full of open problems with a communication-complexity flavor. We will discuss a few such problems that arise in the study of private information retrieval, multi-party secure computation and secret-sharing. In all these cases, there is a huge (exponential or worse) gap between the best known upper and lower bounds. We will describe a recently discovered connection between private information retrieval and secret sharing, and a new secret-sharing scheme for general access structures that breaks a long-conjectured exponential barrier.

Based on joint work with Tianren Liu and Hoeteck Wee.